# 30/100 链表-两两交换链表中的节点
# leetcode第24题: https://leetcode.cn/problems/swap-nodes-in-pairs/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/24
from typing import Optional
from leetcode.bds import ListNode, ListConvert
from leetcode import test


def swapPairs(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return ListConvert.link_to_list(None)
    if not head.next:
        return ListConvert.link_to_list(head)

    head = ListNode(-1, head)  # 构建一个伪头结点
    prev, curr, post = head, head.next, head.next.next
    while post:
        prev.next, curr.next, post.next = post, post.next, curr
        if curr.next:
            prev, curr, post = curr, curr.next, curr.next.next
        else:
            return ListConvert.link_to_list(head.next)


def swapPairs_opt(head: Optional[ListNode]) -> Optional[ListNode]:
    dummy_head = ListNode(-1)  # 构建一个伪头结点
    dummy_head.next = head
    curr = dummy_head
    while curr.next and curr.next.next:
        node1 = curr.next
        node2 = curr.next.next
        curr.next = node2
        node1.next = node2.next
        node2.next = node1
        curr = node1
    return ListConvert.link_to_list(dummy_head.next)


if __name__ == '__main__':
    head1 = ListConvert.list_to_link([1, 2, 3, 4])
    head2 = ListConvert.list_to_link([])
    head3 = ListConvert.list_to_link([1])
    head4 = ListConvert.list_to_link([1, 2])

    inp = [{"head": head1}, {"head": head2}, {"head": head3}, {"head": head4}, ]
    out = [[2, 1, 4, 3], [], [1], [2, 1]]

    test.test_function(swapPairs, inp, out)
    test.test_function(swapPairs_opt, inp, out)
